java循环以获取与输入值最接近的对象

Question

我有一门火星课程：

public abstract class Martian implements Cloneable {
int id;

public Martian(int id) {
    this.id = id;
}
public Object clone() throws CloneNotSupportedException {
    return super.clone();
}
public int getId() {
    return id;
}
public boolean equals(Object o){
    if( o != null);
    return this.getId() == ((Martian)o).getId();    
}
public abstract void speak();

public String toString(){
    return "Martian" + getId(); 
}       
} 

还有一个火星经理课程：

public class MartianManager {
private ArrayList<Martian> martians;
private ArrayList<Martian> teleporters;

public void addMartian(Martian m) {
    martians.add(m);
    if(m instanceof GreenMartian)
        teleporters.add(m);
}
//public Object clone() {

public Martian getMartianClosestToID(int id) {

}
public void groupSpeak() {
    for(Martian m : martians) {
        m.speak();
    }
}
public void groupTeleport(String dest) {
    for (Martian m : martians){
        if (m instanceof GreenMartian)
            ((GreenMartian) m).teleport(dest);
    }   
}
//public obliterateTeleporters() 

//removeMartian(int id)
}

在MartianManager类中，我有一个方法getMartianClosestToId()，它返回的火星人的id与输入id最接近。我的问题基本上是，在循环中使用什么最简单的逻辑来实现这一点，或者它们是一种更简单的方法，比如compareTo，我不知道在这种情况下比较是否有效

Answer 1

这不是最简单的，但在很多情况下，这将是最快的

如果你愿意让你的火星人列表始终按id排序（如果你不经常添加火星人，这很容易做到，你可以在添加火星人时进行排序），你可以这样做：

Comparator<Martian> compareById = new Comparator<Martian>() {
    public int compare(Martian a, Martian b) {
        return Integer.compare(a.getId(), b.getId());
    }
}

然后你可以在你的列表中使用二进制搜索来找到它在列表中被插入的位置

int location = Collections.binarySearch(martians, idToGetClosestTo, compareById);

现在，你将有它应该去的地方，你将有五个选项之一：

1. 这个位置有你要找的id。如果是，返回火星人。获取（位置）
2. 提供的位置不在列表中，这意味着你正在寻找低于最低或高于最高的位置。 2.a.低于最低水平：返回最低水平，火星人。得到（0）； 2.b.高于最高点：返回最高点，火星人。get（martians.length（）-1）
3. 该位置高于您要查找的id。（不会更低，否则你会得到比你做的低1的结果！）看看火星人。获取（位置）和火星人。获取（位置-1）并查看最接近的位置，然后返回相应的位置

这有一个昂贵的前期成本（排序），但在你把它排序后，你可以使用二进制搜索，这是非常便宜的，每次都可以非常快地找到最近的火星人

如果你打算经常添加，那么我建议在末尾添加新的火星人，并将你的收藏标记为未排序，然后只在你即将找到一个时进行排序

public Martian getMartianClosestToID(int id) {
    if(!martiansAreSorted) Collections.sort(martians,compareById);
    int loc = Collections.binarySearch(martians,id,compareById);
    if(loc >= 0) return martians.get(loc); // found exact match
    // we know loc is negative because it wasn't found - read the docs
    loc = -loc;
    if(loc == 0) return martians.get(0);
    if(loc == martians.size()) return martians.get(loc - 1);
    Martian high = martians.get(loc);
    Martian low = martians.get(loc - 1);

    int highid = high.getId();
    int lowid = low.getId();

    int highdiff = Math.abs(id - highid);
    int lowdiff = Math.abs(id - lowid);

    if(highdiff < lowdiff) return high;
    return low;

}

Answer 2

这样的办法应该行得通

这是否正是你想要的取决于一些假设。ID是唯一的吗？火星人能离自己最近吗？如果有两个同样接近的火星人呢？或者没有其他火星人？我假设'id'参数可能是集合中的一个id，而您不想要那个

但最大的问题是：“最近的”是什么意思？“亲密度”的概念通常不适用于IDs

public Martian getMartianClosestToId(int id) {
    Martian closest = null;
    int leastDist = -1;
    for(Martian m : martians) {
        int mId = m.getId();
        if(mId == id)
             continue; // Skip the Martian with the same id.
        int d = Math.abs(mId - id);
        if(leastDist == -1 || d < leastDist) {
            leastDist = d;
            closest = m;
        }
    }
    return closest;
}

我还没有编译/测试过这个——你可能需要修复打字错误

Answer 3

我认为这比目前为止的其他答案更简单（OP要求“最简单的逻辑”）：

public Martian getMartianClosestToID(int id)
{
    if (martians == null || martians.isEmpty())
        return null;

    Martian result = martians.get(0);

    for (Martian m : martians)
        if (Math.abs(id - m.getId()) < Math.abs(id - result.getId()))
            result = m;

    return result
}